Jupyter at Bryn Mawr College
Public notebooks:
/services/public/dblank
/
CS206 Data Structures
/
2017-Spring
/
Notebooks
1. Data Structure Review
¶
Spring 2016, Blank
Bryn Mawr College
"Data Structures: Abstraction and Design Using Java", by Koffman & Wolfgang
1.1 Data Structures
¶
List interface (page 61, 124)
LinkedList (page 88)
Double-Linked List (page 99)
Circular List (page 99)
Node (page 90)
ArrayList (page 62)
Queue (page 195)
Stack (page 149)
Double-ended Queue ("Deque", pronounced "deck") (page 217)
Tree (page 295)
Binary Tree (page 298)
Binary Search Tree (page 300)
Set (page 362)
Map (page 367)
Hashes, Hash Table (page 372)
Open addressing (page 374)
Chaining (page 379)
Collision (page 377)
Linear Probe (page 374)
Quadratic Probe (page 378)
Navigable Set and Map (page 408)
Graph (page 541)
Directed (page 543)
Undirected (page 543)
Path, Cycles, (page 544)
Breadth-First Search (page 560)
Depth-First Search (page 566)
Dijkstra's Algorithm (page 582)
Minimum Spanning Tree (page 584)
1.2 Java
¶
javac compiler
java runtime and command-line arguments
junit testing
eclipse
1.3 Sorting
¶
Bubble Sort (page 428)
Double Trouble (similar to Selection Sort, page 426)
Quicksort (page 451)
1.4 Terms and Concepts
¶
ADT (page 2)
JVM (page 2)
Java API (page 2)
Interface (page 3)
implements (page 6)
instantiate and interface (page 7)
Object-Oriented Programming )page 8)
superclass and subclass (page 9)
this (page 10)
data fields (page 11)
super(...) (page 11)
no-parameter constructor (page 12)
is-a vs. has-a (page 13)
polymorphism (page 19)
abstract classes (page 22)
multiple interfaces (page 26)
primitive type (page 602)
wrappers for primitive types (page 24)
casting (page 27)
toString() (page 28)
instanceof (page 31)
private/protected/public (page 44)
hierarchy (page 46)
factory method (page 52)
generics, generic collection (page 66)
Big-O notation (page 80)
enhanced for statement (Type var: collection) (page 110)
Collection interface (page 121)
generic types (page 127)
recursion (page 243)
stack overflow (page 253)
recursion vs. iteration (page 255)
recursive gcd (page 254)
linear and binary search (page 260)
breadth-first search, binary tree (page 357)
1.5 Errors and Exception Handling
¶
Null Pointer (page 35)
Array Index Out of Bounds ((page 35)
try/catch (page 39)
throw (page 41)
1.6 Bonus Terms
¶
iterator (page 105)
ListIterator - page (page 108)
inner classes: static and nonstatic (page 120)
testing (page 130)
testing: preconditions/postconditions (page 137)
pseudorandom numbers (page 233)
Huffman Tree (page 299)
Heap (page 332)
Priority Queue (page 332)
2-3 Trees (page 503)
B-Trees (page 510)
B+Tree (page 520)
2-3-4 Trees (page 520)